107A - Dorm Water Supply - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define stream(line) istringstream in((line))
#define endl "\n"
#define F first
#define S second
#define clr(a, d) memset((a),d,sizeof(a))
const int MOD = 1e9 + 7;
const int N = 1000 + 5;
const int M = 2000 + 5;

void print_vector(vector<ll> &v) {
    for (ll i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;
}


int head[N],to[M], nxt[M], cost[M], vis[N],n,m, mn, last, ne, indeg[N], have[N];

void addEdge(int f,int t, int c){
    to[ne]=t;
    cost[ne] = c;
    nxt[ne]=head[f];
    head[f]=ne++;
}
void init(){
    memset(head,-1,sizeof(head));
    ne=0;
}
void addBiEdge(int u,int v, int w){
    addEdge(u,v,w);
}
void dfs(int u){
    vis[u] = 1;
    last = u;
    for (int e = head[u],v,w; ~e&&(v=to[e],1) && (w = cost[e],1) ; e=nxt[e]) {
        if(!vis[v]){
            dfs(v);
            if(w < mn){
                mn = w;
            }
        }
    }
}


int main() {
    fast
    int tc =1;
    //cin >> tc;
    while(tc--){
        cin >> n >> m;
        init();
        for (int i = 0; i < m; ++i) {
            int u,v,w;
            cin >> u >> v >> w;
            addBiEdge(u,v,w);
            indeg[v]++;
            have[u]++;
            have[v]++;
        }
        vector<pair<pair<int,int>,int>> res;
        for (int i = 1; i <= n; ++i) {
            if(indeg[i] == 0 && have[i] != 0){
                mn = 1e7;
                dfs(i);
                res.push_back({{i,last}, mn});
            }
        }
        cout << res.size() << endl;
        for(auto x : res){
            cout << x.first.first << " " << x.first.second << " " << x.second << endl;
        }
    }
    return 0;
}